package com.cherrish.demo.algorithm.tree.btree;

import java.util.List;

/**
 * @author cherrish
 * @time 2019-02-21 11:13
 * @name BTree
 * @desc:
 */
public class BTree<K extends Comparable<K>>{
    private BTNode root;
    private int order;

    public Result find(K key){
        BTNode preNode = null;
        BTNode node = root;
        boolean found = false;
        int i = -1;
        while(null != node && !found){
            i = index(node, key);
            if(node.keys.get(i).equals(key)){
                found = true;
            }else{
                preNode = node;
                node = (BTNode) node.children.get(i);
            }
        }
        return new Result(found ? node : preNode, found, i);
    }


    private int index(BTNode<K> node, K key){
        for(int i = 0; i < node.number; i++){
            if(key.compareTo(node.keys.get(i)) <= 0){
                return i;
            }
        }
        return node.number;
    }

    private void split(BTNode<K> node, int s, BTNode<K> newNode){
        int number = node.number;
        List<K> keys = node.keys;
        List<BTNode> children = node.children;

        node.keys = keys.subList(0, s-1);
        node.children = (children.subList(0, s));
        node.number = (s-1);

        newNode.keys = (keys.subList(s, number-1));
        newNode.children = (children.subList(s, number));
        newNode.number = (number-s);
    }
    private BTNode newRoot(K key){
        BTNode node = new BTNode();
        node.keys.add(0, key);
        node.children.add(0, null);
        node.children.add(1, null);
        node.number = 1;
        return node;
    }

    static class Result{
        protected BTNode node;
        protected boolean found;
        protected int index;

        public Result(BTNode node, boolean found, int index) {
            this.node = node;
            this.found = found;
            this.index = index;
        }
    }
}
